package com.tal.algorithms.tree.binarysearchtree;

import java.util.Objects;

public class RedBlackTree<T extends Comparable> {

    private RedBlackTree left;
    private RedBlackTree right;
    private RedBlackTree parent;
    private Node node;
    private boolean red;

    public RedBlackTree(Node node) {
        this.node = node;
    }


    public void insert(RedBlackTree<T> root, Node node){
        RedBlackTree y = null;
        RedBlackTree x = root;
        while (x != null) {
            y = x;
            if (node.getKey().compareTo(x.getNode().getKey()) < 0) {
                x = x.getLeft();
            } else {
                x = x.getRight();
            }
        }
        RedBlackTree<T> rbTreeZ = new RedBlackTree(node);
        rbTreeZ.setParent(y);
        if (y == null) {
            //根节点
            root = rbTreeZ;
        } else if (rbTreeZ.getNode().getKey().compareTo(y.getNode().getKey()) < 0) {
            y.left = rbTreeZ;
        } else {
            y.right = rbTreeZ;
        }

        rbTreeZ.setLeft(null);
        rbTreeZ.setRight(null);
        rbTreeZ.setRed(true);
        rbInsertFixUp(rbTreeZ);
    }

    private void rbInsertFixUp(RedBlackTree<T> rbTreeZ) {
        while (rbTreeZ.getParent().isRed()) {
            if (rbTreeZ.getParent().getNode().equals(rbTreeZ.getParent().getParent().getLeft().getNode())) {

            }
        }
    }


    /**
     * 旋转
     */
    private void rotateLeft(RedBlackTree<T> x) {
        if (x != null && x.getLeft() != null) {
            RedBlackTree y = x.getLeft();
            x.right = y.left;
            if (y.left != null) {
                y.left.parent = x;
            }
            y.parent = x.parent;
            if (x.parent == null) {
                //如果用root，能进这里表示x是root，旋转之后y是root。
            } else if (x.parent.left != null && x.getNode().equals(x.parent.left.getNode())) {
                //如果x是左树
                x.getParent().setLeft(y);
            } else {
                //如果x是右树
                x.getParent().setRight(y);
            }
            y.left = x;
            x.parent = y;
        }
    }

    private void rotateRight(RedBlackTree<T> y) {
        if (y != null && y.getLeft() != null) {
            RedBlackTree x = y.getRight();
            y.left = x.right;
            if (x.right != null) {
                x.right.parent = y;
            }
            x.parent = y.parent;
            if (y.parent == null) {
                //如果用root，能进这里表示x是root，旋转之后y是root。
            } else if (y.parent.left != null && y.getNode().equals(y.parent.left.getNode())) {
                //如果y是左树
                y.getParent().setLeft(x);
            } else {
                //如果y是右树
                y.getParent().setRight(x);
            }
            x.right = y;
            y.parent = x;
        }
    }

    /**
     * 递归实现，资源消耗往往比较高
     */
    public RedBlackTree search(Node searchNode) {
        return search(this, searchNode);
    }

    public RedBlackTree search(RedBlackTree rbTree,Node searchNode) {
        if (searchNode == null || rbTree == null || searchNode.equals(rbTree.getNode())) {
            return rbTree;
        }
        if (searchNode.getKey().compareTo(rbTree.getNode().getKey()) < 0) {
            return search(rbTree.getLeft(), searchNode);
        } else {
            return search(rbTree.getRight(), searchNode);
        }
    }

    /**
     * 迭代的方式往往更加省力
     */
    public RedBlackTree iterativeTreeSearch(RedBlackTree rbTree,Node searchNode) {
        while (rbTree != null && !searchNode.equals(rbTree.getNode())) {
            if (searchNode.getKey().compareTo(rbTree.getNode().getKey())  < 0) {
                rbTree = rbTree.getLeft();
            } else {
                rbTree = rbTree.getRight();
            }
        }
        return rbTree;
    }

    public RedBlackTree iterativeTreeSearch(Node searchNode) {
        return iterativeTreeSearch(this, searchNode);
    }

    public RedBlackTree getMin() {
        RedBlackTree rbTree = this;
        while (rbTree.getLeft() != null) {
            rbTree = rbTree.getLeft();
        }
        return rbTree;
    }

    public RedBlackTree getMax() {
        RedBlackTree rbTree = this;
        while (rbTree.getRight() != null) {
            rbTree = rbTree.getRight();
        }
        return rbTree;
    }

    class Node {
        T key;

        public T getKey() {
            return key;
        }

        public void setKey(T key) {
            this.key = key;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return Objects.equals(key, node.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }

    public boolean isRed() {
        return red;
    }

    public void setRed(boolean red) {
        this.red = red;
    }

    public RedBlackTree getLeft() {
        return left;
    }

    public void setLeft(RedBlackTree left) {
        this.left = left;
    }

    public RedBlackTree getRight() {
        return right;
    }

    public void setRight(RedBlackTree right) {
        this.right = right;
    }

    public RedBlackTree getParent() {
        return parent;
    }

    public void setParent(RedBlackTree parent) {
        this.parent = parent;
    }

    public Node getNode() {
        return node;
    }

    public void setNode(Node node) {
        this.node = node;
    }
}
